package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by Ghost on 2014/10/16 0016.
 */
public class Binary_Tree_Zigzag_Level_Order_Traversal {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        ArrayList<List<Integer>> rst = new ArrayList<List<Integer>>();
        if(root==null)
            return rst;
        int size = 0;
        boolean left = false;
        queue.add(root);
        while(!queue.isEmpty()){
            left = !left;
            size = queue.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            for(;size>0;size--){
                TreeNode node = queue.poll();
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
                tmp.add(node.val);
            }
            if(left){
                rst.add(tmp);
            }
            else{
                ArrayList<Integer> ttmp = new ArrayList<Integer>();
                for(int i=tmp.size()-1;i>=0;i--){
                    ttmp.add(tmp.get(i));
                }
                rst.add(ttmp);
            }
        }
        return rst;
    }
    public static void main(String[] args){
        TreeNode head = new TreeNode(3);
        /*head.left = new TreeNode(9);
        head.right = new TreeNode(20);
        head.right.left = new TreeNode(15);
        head.right.right = new TreeNode(7);*/

        Binary_Tree_Zigzag_Level_Order_Traversal binary_tree_zigzag_level_order_traversal = new Binary_Tree_Zigzag_Level_Order_Traversal();
        List<List<Integer>> list = binary_tree_zigzag_level_order_traversal.zigzagLevelOrder(head);
        for(List<Integer> tmp:list){
            for(Integer integer:tmp){
                System.out.print(" "+integer);
            }
            System.out.println();
        }

    }
}
